The present invention relates to a method of improving a placement to be used in a layout design of such as a printed wiring board or a very large scale integrated circuit (VLSI) chip.
The term "layout design" generally means to place blocks according to a logic connection and interconnect the blocks. A layout design result is obtainable upon mutual influences between a certain wiring result and other wiring results. Therefore, an evaluation of a placement result is performed by taking a routability into consideration.
As methods related to an automatic routing, a channel router, a line-search and a maze router are well known. For details of these methods, reference is made to an article by Gary Robson titled "Automatic Placement and Routing of Gate Arrays", VLSI DESIGN, vol. 5, No. 4, April issue, 1984, pp. 35 to 43 (Reference 1).
In the channel router, among others, wirings penetrate channels vertically and, therefore, it is necessary to preliminarily determine positions at which the wirings penetrate the channels. In order to realize this, a vertical assignment is performed initially. Another method in which wiring routes are roughly determined prior to the vertical assignment and the line search, i.e., the so-called a global router, is also well known.
Examples of wirings according to the methods are disclosed in an article by C. P. Hsu et al titled "ALPS2 A Standard Cell Layout System for Double-Layer Metal Technology" in the preliminary papers of the 22nd ACM/IEEE DESIGN AUTOMATION CONFERENCE held in June 23 to 26, 1985 (Reference 2).
In the proposed system, wiring routes are roughly determined by the global routing after a placement and then cross points of the respective wirings and cell columns are obtained by the vertical assignment. Then, the "One-dimensional Placement Improvement" method described on page 445 in Reference 2 is performed again and the wirings are performed by using the channel router thereafter.
In the "One-dimensional Placement Improvement", one of the cell rows is considered and blocks in that row are swapped by taking channel density, routability and wire length into consideration. Then, the cross location between the wirings and the cell rows are obtained again by using a method similar to the Vertical Assignment. This procedure is performed for all cell rows.
In this method, however, the cross location between the cell rows and the wirings determined by the initial "Vertical assignment" such that the vertical line connecting the cross locations is as straight as possible are modified by the "One-dimensional Placement Improvement". Even if such correction is performed by a similar method to the "Vertical Assignment", it is impossible to consider a balance as a whole in this stage because the certain cell row is considered and thus there is a tendency of distortion of wiring. Therefore, the wiring which penetrates vertically may be zig-zagged at a time when the channel router is applied finally, resulting in a necessity of extra wiring area: